﻿#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
#include<thread>
#include<mutex>
#include<algorithm>
#include<unordered_map>
#include"ObjectPool.h"
#include <atomic>
#include<map>
using std::cout;
using std::endl;
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#endif // _WIN64

#if defined(_WIN32) || defined(_WIN64)
#include<windows.h>
#else
// linux :brk,mmap
#endif

// 直接去堆上按页申请空间
inline static void* SystemAlloc(size_t kpage)
{
#if defined(_WIN32) || defined(_WIN64)
	//LPVOID VirtualAlloc(
	//	LPVOID lpAddress,      // 期望的内存起始地址（通常设为 NULL，由系统决定）
	//	SIZE_T dwSize,         // 要分配的内存大小（字节）
	//	DWORD  flAllocationType, // 分配类型（MEM_COMMIT | MEM_RESERVE）
	//	DWORD  flProtect       // 内存保护权限（PAGE_READWRITE 等）
	//);
	//// 分配 1MB 可读写的内存
	//void* pMem = VirtualAlloc(
	//	NULL,                   // 让系统自动选择地址
	//	1024 * 1024,            // 1MB
	//	MEM_COMMIT | MEM_RESERVE, // 提交并保留物理内存
	//	PAGE_READWRITE          // 可读写
	//);

	//一页是8kb
	void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif

	if (ptr == nullptr)
		throw std::bad_alloc();

	return ptr;
}
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}
//threadCache 中最大内存块
static const size_t MAX_BYTES = 256 * 1024;
//threadCache 中桶的个数
static const size_t NFREELIST = 208;
//pageCache 中页的数量
static const size_t NPAGES = 129;
// ⻚⼤⼩转换偏移, ⼀⻚定义为2^13,也就是8KB
static const size_t PAGE_SHIFT = 13;

static void*& NextObj(void* obj)
{
	return *(void**)obj;
}
// 管理切分好的小对象的自由链表
class FreeList
{
public:
	void Push(void* obj)
	{
		//头插
		NextObj(obj) = _freeList;
		_freeList = obj;
		_size++;
	}
	void* Pop()
	{
		assert(_freeList);
		//头删
		void* obj = _freeList;
		_freeList = NextObj(_freeList);
		_size--;
		return obj;
	}
	bool Empty()
	{
		return _freeList == nullptr;
	}
	size_t& MaxSize()
	{
		return _maxSize;
	}

	void PushRange(void* start, void* end,size_t n)
	{
		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}
	void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n <= _size);
		start = _freeList;
		end = _freeList;
		int j = 0;
		for (size_t i = 0; i < n-1; ++i)
		{
			j++;
			end = NextObj(end);
		}

		//剩余的节点
		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}

	size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

//减少内碎片的浪费
// 计算对象大小的对齐映射规则
class SizeClass
{
	// 整体控制在最多10%左右的内碎片浪费
// [1,128]					8byte对齐	    freelist[0,16)
// [128+1,1024]				16byte对齐	    freelist[16,72)
// [1024+1,8*1024]			128byte对齐	    freelist[72,128)
// [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
// [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)
public:
	//计算对齐后的内存数
	//size_t _RoundUp(size_t size, size_t alignNum)//alignNum 对其数
	//{
	//	if (size % alignNum != 0)
	//	{
	//		return (size / alignNum + 1) * alignNum;
	//	}
	//	else
	//	{
	//		return size;
	//	}
	//}

	//计算对齐后的内存数
	static inline size_t _RoundUp(size_t bytes, size_t alignNum)
	{
		return ((bytes + alignNum - 1) & ~(alignNum - 1));
		//  (1  +  7)&(~7)=01000&11000=8
		//		.
		//		.
		//  (8  +  7)&(~7)=01111&11000=8
		// 
		//  (9  +  7)&(~7)=010000&111000=16
		//		.
		//		.
		//  (16  +  7)&(~7)=010111&111000=16
	}
	static inline size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			return _RoundUp(size, 1 << PAGE_SHIFT);
		}
	}
	// 计算映射的哪一个自由链表桶
	//size_t _Index(size_t bytes, size_t alignNum)
	//{
	//	if (bytes % alignNum != 0)
	//	{
	//		return bytes / alignNum;
	//	}
	//	else
	//	{
	//		return bytes / alignNum - 1;
	//	}
	//}

	// 计算映射的哪一个自由链表桶(相对的)
	static inline size_t _Index(size_t bytes, size_t align_shift)//align_shift 2^n  n=align_shift 
	{
		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
		//		    (1  +  7)>>3-1=0号桶
		//		    (8  +  7)>>3-1=0号桶->0111>>3 -1=0
		//		    (9  +  7)>>3-1=0号桶->010000>>3 -1=2-1=1;
		//		    (16 +  7)>>3-1=0号桶->010111>>3 -1=2-1=1;
	}
	static inline size_t Index(size_t bytes)
	{
		assert(bytes < MAX_BYTES);
		// 每个区间有多少个链
		static int group_array[4] = { 16, 56, 56, 56 };
		if (bytes <= 128)
		{
			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + group_array[0];
		}
		else if (bytes <= 8 * 1024)
		{
			return _Index(bytes - 1024, 7) + group_array[0] + group_array[1];
		}
		else if (bytes <= 64 * 1024)
		{
			return _Index(bytes - 8 * 1024, 10) + group_array[0] + group_array[1] + group_array[2];
		}
		else if (bytes <= 256 * 1024)
		{
			return _Index(bytes - 64 * 1024, 13) + group_array[0] + group_array[1] + group_array[2] + group_array[3];
		}
		else
		{
			assert(false);
		}
		return -1;
	}
};

// 一次thread cache从中心缓存获取多少个size大小的内存
static size_t NumMoveSize(size_t size)
{
	assert(size > 0);
	// [2, 512]，一次批量移动多少个对象的(慢启动)上限值
	// 小对象一次批量上限高
	// 小对象一次批量上限低
	int num = MAX_BYTES / size;
	if (num < 2)
	{
		num = 2;
	}
	if (num > 512)
	{
		num = 512;
	}
	return num;
}
// 计算⼀次向系统获取⼏个⻚
// 单个对象 8byte
// ...
// 单个对象 256KB
static size_t NumMovePage(size_t size)
{
	size_t num = NumMoveSize(size);
	size_t npage = num * size;
	npage >>= PAGE_SHIFT;
	if (npage == 0)
		npage = 1;
	return npage;
}
// 管理多个连续页大块内存跨度结构
class Span
{
public:
	PAGE_ID _pageId = 0;		// 大块内存起始页的页号
	size_t _n = 0;				// 页的数量

	Span* _prev = nullptr;		// 双向链表的结构
	Span* _next = nullptr;

	size_t _objSize = 0;		//切好的小块内存大小
	
	size_t _useCount = 0;		// 切好小块内存，被分配给thread cache的计数
	void* _freeList = nullptr;	// 切好的小块内存的自由链表
	bool _isUse = false;		// 是否在被使用
};

// 带头双向循环链表
class SpanList {
public:
	SpanList() {
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	Span* Begin()
	{
		return _head->_next;
	}
	Span* End()
	{
		return _head;
	}
	void PushFront(Span* span)
	{
		Insert(Begin(), span);
	}
	Span* PopFront()
	{
		Span* span = _head->_next;
		Erase(span);
		return span;
	}
	void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		Span* prev = pos->_prev;
		prev->_next = newSpan;
		newSpan->_prev = prev;
		newSpan->_next = pos;
		pos->_prev = newSpan;
	}
	void Erase(Span* pos)
	{
		assert(pos);
		//assert(pos != _head);
		if (pos == _head)
		{
			int x = 0;
		}
		Span* prev = pos->_prev;
		Span* next = pos->_next;

		prev->_next = next;
		next->_prev = prev;
	}
	bool Empty()
	{
		return _head->_next == _head;
	}
private:
	Span* _head;
public:
	std::mutex _mtx; //桶锁
};